1. Field of the Invention
This invention relates to method and apparatus for generating an error correction code for correcting errors in data, and more particularly, a method and apparatus for generating an error location polynomial table used to locate errors in data which has been encoded using a Reed-Solomon error correction technique.
2. Description of Related Art
Data which is either stored or communicated is susceptible to errors. Errors corrupt the value of the data and thereby obscure the original value. Therefore, in situations in which the exact value of data is required to be reliably determined, a means must be provided by which the original value of the data can be determined after the data has been read from a storage device or after received by a device at the receiving end of a communication path.
One means for determining the original value of data which has been corrupted is commonly referred to as Reed-Solomon error detection and correction. Reed-Solomon error detection and correction requires that the data initially be encoded. Data is grouped into information symbols which form Reed-Solomon blocks. The universe of all possible symbols is referred to as the "finite field". For example, forward error correction (FEC) used in Cellular Digital Packet Data (CDPD) is performed by transmitting information encoded in Reed-Solomon blocks comprising 47 information symbols of 6 bits each followed by 16 parity symbols of 6 bits each.
In accordance with Reed-Solomon encoding, the finite field is "closed", meaning that the product or sum of any two symbols within the finite field is another symbol within the finite field. Reed-Solomon encoding schemes are characterized by the total number of symbols n in an RS block, where n=2.sup.m -1 and m is the number of bits in each symbol, and the total number of information symbols in each block is k. A Reed-Solomon code is typically referred to as RS(n, k). Accordingly, a Reed-Solomon code in which symbols have 6 bits, and thus a total number of symbols in a block is equal to 63, and a total number of information symbols in each block is equal to 47 is referred to as RS(63, 47). It is well known in the art that the number of errors that can theoretically be corrected in a RS(n, k) encoding is (n-k)/2=t. Accordingly, 8 errors can theoretically be corrected using an RS(63, 47) code having 2t=16 additional (i.e., "parity") symbols in each block of 63.
Once the information has been mapped into a transmit vector and the transmit vector has been either stored or transmitted, errors which occur in the transmit vector can be detected and corrected by generating an error location polynomial .sigma.(X). The value of the error location polynomial is determined by one of several well known algorithms. One of these algorithms is known as "Berlekamp's iterative algorithm".
In accordance with Berlekamp's iterative algorithm the first step is to find a first minimum-degree polynomial .sigma..sup.(1) (X) whose coefficients satisfy a first Newton's identity. It should be noted that the superscript "(1)" indicates that this is the first minimum degree polynomial, as opposed to the second, third polynomial, etc., as will become apparent below. Details regarding the nature of the Newton's identity are provided in Error Control Coding: Fundamentals and Applications, by Shu Lin and Daniel J. Costello, Jr. (Prentice-Hall, 1983) which is herein incorporated by reference. Lin and Costello disclose a method for generating the values .sigma..sup.(.mu.) (X) by generating a series of "syndrome" components using a well known algorithm. The syndrome components are then used to generate "discrepancies", d.sub..mu.. If d.sub..mu. =0, then the coefficients of .sigma..sup.(.mu.) (X) satisfy the (.mu.+1).sup.th Newton's identity. Therefore: EQU .sigma..sup.(.mu.-1) (X)=.sigma..sup.(.mu.)
The next step is to test whether the coefficients of .sigma..sup.(1) (X) satisfy a second Newton's identity. If the coefficients of .sigma..sup.(1) (X) satisfy the second Newton's identity (i.e., d.sup.1 =0), then the value of a second minimum-degree polynomial .sigma..sup.(2) (X) is equal to the value of the first minimum-degree polynomial .sigma..sup.(1) (X). However, if the second Newton's identity is not satisfied by the first minimum-degree polynomial .sigma..sup.(1) (X) (i.e., d.sup.1 not equal to 0), then a correction term is added to .sigma..sup.(1) (X) to form .sigma..sup.(2) (X), such that .sigma..sup.(2) (X) has minimum degree and its coefficients satisfy the first two Newton's identities. Therefore, at the end of the second step of iteration, a minimum-degree polynomial .sigma..sup.(2) (X) has been obtained whose coefficients satisfy the first two Newton's identities. The third step is to find a minimum-degree polynomial .sigma..sup.(3) (X) from .sigma..sup.(2) (X), such that the coefficients of .sigma..sup.(3) (X) satisfy the third Newton's identity. If the coefficients of .sigma..sup.(2) (X) satisfy the first three Newton's identities (i.e., d.sup.2 =0), then .rho..sup.(3) (X)=.sigma..sup.(2) (X). If not, then a correction term is added to .sigma..sup.(2) (X) to form .sigma..sup.(3) (X). Iterations continue until each minimum-degree polynomial through .sigma..sup.(2t) (X) has been generated. The polynomial .sigma..sup.(2t) (X) is equal to the error location polynomial .sigma.(X). The error location polynomial .sigma.(X) yields an error pattern e(X) which can be used to determine the location of the errors in a received polynomial r(X), if the number of errors in the received polynomial is no greater then t.
The syndrome components are generated using a well known algorithm disclosed by Lin and Costello. The syndrome components are then used to generate the discrepancies, d.sub..mu..
If d.sub..mu. is not equal to zero, (i.e., the coefficients of .sigma..sup.(.mu.) (X) do not satisfy the (.mu.+1).sup.th Newton's identity) then a correction term must be added to .sigma..sup.(.mu.) (X) to obtain .sigma..sup.(.mu.+1) (X). To determine the value of this correction term, each previously generated polynomial .sigma..sup.(.mu.) (X) must be analyzed to determine which polynomial .sigma..sup.(.rho.) (X) has the largest degree (i.e., the greatest exponent of X) and has a corresponding .sigma..sup.th discrepancy d.sub..rho. not equal to zero. The value .rho. identifies a previously completed row of values within the error location polynomial table.
One way to organize this process is to generate an error location polynomial table, such as Table 1, in which for each value of .mu. there is an associated minimum-degree polynomial .sigma..sup.(.mu.) (X), a .mu..sup.th discrepancy d.sub..mu., a value 1.sub..mu. equal to the degree of the polynomial .sigma..sup.(.mu.) (X), and a value .mu.-1.sub..mu..
TABLE 1 ______________________________________ .mu. .sigma..sup.(.mu.) (X) d.sub..mu. l.sub..mu. .mu. - l.sub..mu. ______________________________________ -1 1 1 0 -1 0 1 .alpha..sup.12 0 0 1 1 + .alpha..sup.12 X .alpha..sup.7 1 0 (take .rho. = -1) 2 1 + .alpha..sup.3 X 1 1 1 (take .rho. = 0) 3 1 + .alpha..sup.3 X + .alpha..sup.3 X.sup.2 .alpha..sup.7 2 1 (take .rho. = 0) 4 1 + .alpha..sup.4 X + .alpha..sup.12 X.sup.2 .alpha..sup.10 2 2 (take .rho. = 2) 5 1 + .alpha..sup.7 X + .alpha..sup.4 X.sup.2 + .alpha..sup.6 0.sup.3 2 (take .rho. = 3) 6 1 + .alpha..sup.7 X + .alpha..sup.4 X.sup.2 + .alpha..sup.6 X.sup.3 -- -- -- ______________________________________
The is generated by initializing the table with the values of the first two rows, as shown in Table 2.
TABLE 2 ______________________________________ .mu. .sigma..sup.(.mu.) (X) d.sub..mu. l.sub..mu. .mu. - l.sub..mu. ______________________________________ -1 1 1 0 -1 0 1 S.sub.1 0 0 2 3 4 5 6 ______________________________________
The values of Table 1 have been determined by assuming a triple-error correcting Reed-Solomon code RS(15, 9) with symbols from the Galios Field GF(2.sup.4). In addition, it is assumed that an all zeros vector is transmitted and a vector r=(0 0 0 .alpha..sup.7 0 0 .alpha..sup.3 0 0 0 0 0 .alpha..sup.4 0 0) is received having three errors. It should be noted that while there are considered to be only three errors, each of the three errors represents a change of state of more than one bit within the receive vector. For example, the 4-tuple representation of .alpha..sup.7 is 1101. Therefore, three bits have changed state between transmission and reception, resulting in one errored symbol.
The polynomial representation of the receive vector is r(X)=.alpha..sup.7 X.sup.3 +.alpha..sup.3 X.sup.6 +.alpha..sup.4 X.sup.12. The polynomial representation of the receive vector is formed as a sum of products of each power representation and X raised to a power, the power to which X is raised being equal to the location of the power representation within the receive polynomial. In the present example, the first product is .alpha..sup.7 X.sup.3 because the sum of the first three products are each equal to zero (i.e., 0.multidot.1+0.multidot.X+0.multidot.X.sup.2 =0). In the present case, since all zeros were transmitted, the polynomial r(X) has only three components, each of which represent an erroneous symbol and its location. Syndrome components are created from the polynomial r(X) as follows: EQU S.sub.1 =r(.alpha.)=.alpha..sup.10 +.alpha..sup.9 +.alpha.=.alpha..sup.12(EQ. 2) EQU S.sub.2 =r(.alpha..sup.2)=.alpha..sup.13 +1+.alpha..sup.13 =1(EQ. 3) EQU S.sub.3 =r(.alpha..sup.3)=.alpha.+.alpha..sup.6 +.alpha..sup.10 =.alpha..sup.14 (EQ. 4) EQU S.sub.4 =r(.alpha..sup.4)=.alpha..sup.4 +.alpha..sup.12 +.alpha..sup.7 =.alpha..sup.10 (EQ. 5) EQU S.sub.5 =r(.alpha..sup.5)=.alpha..sup.7 +.alpha..sup.3 +.alpha..sup.4 =0(EQ. 6) EQU S.sub.6 =r(.alpha..sup.6)=.alpha..sup.10 +.alpha..sup.9 +.alpha.=.alpha..sup.12 (EQ. 7)
It should be noted that multiplication of a base raised to a power (commonly referred to as a power representation) by a second power representation in a Galios Field is performed by adding the exponents of like bases using modulo n addition, where n is the size of the entire Galios Field (in this case, 16) (e.g., .alpha..sup.7 .alpha..sup.3 =.alpha..sup.10). Furthermore, addition of a first power representation to a second power representation in a Galios Field is performed by looking up the n-tuple representation associated with each power representation and exclusive ORing the n-tuple representations (e.g., .alpha..sup.7 +.alpha..sup.3 =.alpha..sup.4 ; where the 4-tuple representation of .alpha..sup.7 =1101, the 4-tuple representation of .alpha..sup.3 =0001, (1101 XOR 0001)=1100, and the power representation of 1100=.alpha..sup.4). Table 3 provides the power representation and associated 4-tuple representations for each symbol in a Galios Field GF(2.sup.4).
TABLE 3 ______________________________________ Power Representation 4-Tuple Representation ______________________________________ 0 0 0 0 0 1 1 0 0 0 .alpha..sup.1 0 1 0 0 .alpha..sup.2 0 0 1 0 .alpha..sup.3 0 0 0 1 .alpha..sup.4 1 1 0 0 .alpha..sup.5 0 1 1 0 .alpha..sup.6 0 0 1 1 .alpha..sup.7 1 1 0 1 .alpha..sup.8 1 0 1 0 .alpha..sup.9 0 1 0 1 .alpha..sup.10 1 1 1 0 .alpha..sup.11 0 1 1 1 .alpha..sup.12 1 1 1 1 .alpha..sup.13 1 0 1 1 .alpha..sup.14 1 0 0 1 ______________________________________
The syndrome components are then used to calculate discrepancy components d.sub..mu.. As can be seen from Table 2, d.sub.-1 is always equal to 1 and d.sub.0 is always equal to S.sub.1. In the present example, d.sub.0 =S.sub.1 =.alpha..sup.12. Generation of the discrepancy components will be discussed below.
In generating the values of Table 1 according to the Berlekamp iterative algorithm, the next step is to determine the value of .sigma..sup.2 (X). The value of .sigma..sup.(.mu.+1) (X) is calculated by applying the formula: EQU .sigma..sup.(.mu.+1) (X)=.sigma..sup.(.mu.) (X)+(d.sub..mu. /d.sub..rho.).multidot.X.sup.(.mu.-.rho.) .multidot..sigma..sup.(.mu.) (X)(EQ. 8)
where .rho. identifies a previously completed row of values within the error location polynomial table. However, it can be seen that if d.sub..mu. is equal to zero, then: EQU .sigma..sup.(.mu.+1) (X)=.sigma..sup.(.mu.) (X) (EQ. 9)
The value of .rho. is determined by selecting a row which has been completed prior to the .mu..sup.th row, which has both a discrepancy d.sub..rho. which is non-zero, and for which the value of .mu.-1.sub..mu. in the last column (i.e., the right-most column) in the row is greatest in relation to the values in the last column in each other row which was completed prior to the .mu..sup.th row and which has a non-zero discrepancy.
To calculate the value .sigma..sup.(.mu.+1) (X)=.sigma..sup.(1) (X) it should be noted that .mu.+1=1. Therefore .mu.=0, d.sub..mu. =d.sub.0 =S.sub.1 =.alpha..sup.12, and .sigma..sup.(0) (X)=1. Furthermore, since only the row in which the value in the first column is equal to -1 was completed prior to the .mu..sup.th row and has a discrepancy that is not equal to zero, .rho. should be set equal to -1.
By setting .rho.=-1, the values of d.sub..rho. and X.sup.(.mu.-.rho.) can be determined. The value of d.sub..rho. =d.sub.-1 =1. The value of X.sup.(.mu.-.rho.) =X.sup.(0-(-1)) =X. Therefore, the value of .sigma..sup.(1) (X) can be determined by applying equation EQ. 8 as follows: ##EQU1##
This value is then inserted into Table 2, as shown in Table 4.
TABLE 4 ______________________________________ .mu. .sigma..sup.(.mu.) (X) d.sub..mu. l.sub..mu. .mu. - l.sub..mu. ______________________________________ -1 1 1 0 -1 0 1 S.sub.1 0 0 1 1 + .alpha..sup.12 X 3 4 5 6 ______________________________________
Next, the value of d.sub..mu. is calculated for the next row (the row currently being filled in) by applying the following formula: EQU D.sub..mu. =S.sub..mu.+1 +.sigma..sub.1.sup.(.mu.) (X).multidot.S.sub..mu. +.sigma..sub.2.sup.(.mu.) (X).multidot.S.sub..mu.-1 . . . +.sigma..sub.1.sbsb..mu.+1.sup.(.mu.+1) (X).multidot.S.sub..mu.+1-1.mu.+1(EQ. 11)
Wherein .sigma..sub.a.sup.(b) (X) is the a.sup.th coefficient of .sigma..sup.(b) (X) and 1.sub..mu.+1 =1. The polynomial .sigma..sup.(1) (X) has a degree of 1. Accordingly, for the case in which .mu.=1, 1.sub..mu. =1. The other variables of equation EQ. 11 are: S.sub..mu.+1 =S.sub.2 =1, .sigma..sub.1.sup.(.mu.) (X)=.sigma..sub.1.sup.(1) (X)=.alpha..sup.12, S.sub..mu. =S.sub.1 =.alpha..sup.12. It can be seen that d.sub..mu. has only two components, since the degree of .sigma..sup..mu. (X) is one.
Therefore: EQU d.sub..mu. =1+.alpha..sup.12 =1+.alpha..sup.24 =1+.alpha..sup.9 -1 0 0 0 .sym.0 1 0 1=1 1 0 1=.alpha..sup.7 (EQ. 12)
The value .mu.-1.sub..mu. =0 for the .mu..sup.th row. Thus, each of the columns of the third row can be completed.
Next, the values of the fourth row are calculated. First, the value of .sigma..sup.(.mu.+1) (X) is determined, for .mu.=1. If the value of d.sub..mu. were equal to zero, then the value of .sigma..sup.(.mu.+1) (X) would be equal to .sigma..sup.(.mu.) (X). However, since the value of d.sub..mu. is not equal to 0, but rather is equal to d.sub.1 =.alpha..sup.7, a value must be determined for .rho. in order to determine the value of .sigma..sup.(.mu.+1) (X).
Accordingly, a row must be identified which is prior to the .mu..sup.th row and which has both a non-zero value for d.sub..mu. and the greatest value of .mu.-1.sub..mu.. The value presented in the first column from the left of the identified row is selected as the value for .rho.. In the present case in which .mu.=1, the second row (i.e., the row associated with .mu.=0) is selected, and .rho. is set equal to 0. Applying the appropriate formulas, the values shown in the third row are attained in the same manner as was described with respect to the second row.
Next, the values of the fourth row are calculated. The value of .mu. is set to 2. Since the value of d.sub..mu. is not zero, a value must be determined for .rho.. However, at this point in the algorithm, a problem arises in determining the value of .rho.. That is, the value to be selected for .rho. is ambiguous, since there are two rows which each meet the requirements for selection of the value of .rho.. That is, both the second row (.mu.=0) and the third row (.mu.=1) are prior to the .mu..sup.th row, have a value of d.sub..mu. which is non-zero, and have values of .mu.-1.sub..mu. that are zero, zero being the largest value of any row which occurs prior to the .mu..sup.th row. It should be clear that the values associated with the second and third rows are very different and will result in different values for .sigma..sup.(.mu.+1) (X). In fact, if the wrong value is selected for .rho., the error location polynomial that results cannot be used to accurately determine the location of errors in the receive polynomial.
Other such conditions which result in an ambiguity as to the value of .rho. arise which make it impossible for errors to be located and corrected. These ambiguities must be resolved in a manner which ensures that the proper value is selected for .rho., and thus that the proper row is selected when determining the value of .sigma..sup.(.mu.+1) (X) by applying equation EQ. 8 above. However, Lin and Costello do not provide any mechanism for resolving this ambiguity. Therefore, it is assumed that the particular row to be used is either selected arbitrarily or that the first row that satisfies the Lin and Costello criteria is selected.
Accordingly, it would be desirable to provide a method and apparatus which allows accurate selection of the value of .rho. in cases in which more than one row are equally qualified to be selected as the row to be used in calculating the values of additional entries in table, and thus yielding an error location polynomial that can be used to locate and correct t-1 errors effectively in an RS(n, k) code in which n-k=2t.